package org.gzc.sort;


import java.util.Arrays;

/**
 * @Description: 快速排序
 * @Author: guozongchao
 * @Date: 2020/8/8 22:22
 */
public class QuickSort implements SortStrategy{

    private static int count=0;
    @Override
    public void sort(int[] array) {
        quickSort1(array,0,array.length-1);   //经过几轮的8百万的数据测试，发现这个更快速
//        quickSort2(array, 0, array.length - 1);
    }

    /**
     * 实现方法一：选取第一个元素作为基准值，双指针从另一端开始遍历，向基准值一段靠拢（双指针单向交换方式）
     * @param array
     * @param begin
     * @param end
     */
    public void quickSort1(int[] array, int begin, int end) {
        int i = end;  //定义两个指针，指向序列的最后一个元素
        int j = end;
        int pivot=array[begin];   //将序列的第一个元素作为基准值（支点）
        while(i>=begin){
            //i所指向的元素大于或者等于基准值 （i!=j主要判断是不是同一个位置，减少不必要的交换）
            if(array[i]>=pivot) {
                //将i指向的元素与j指向的元素交换
                int temp = array[i];
                array[i] = array[j];
                array[j]=temp;
                j--;
            }
            i--;  //继续往前移动i
        }

        if (begin<j ) {   //如果左侧分区的元素大于1
            quickSort1(array, begin, j);   //对左侧分区进行递归
        }
        if(j+2<end){  //如果右侧分区元素大于1
            quickSort1(array,j+2,end);  //对右侧分区进行递归
        }
    }

    /**
     * 实现方法一：选取第一个元素作为基准值，双指针分别从两端开始遍历，向中间靠拢（双向相向移位方式）
     * @param array
     * @param begin
     * @param end
     */
    public void quickSort2(int[] array, int begin, int end) {
        int i=begin;
        int j=end;
        int pivot = array[begin];
        //指针分别向中间靠拢，直到相遇停止
        while(i<j){
            while(i<j && array[j]>=pivot){
                //指针j从右向左遍历，当j指向的元素大于等于基准值pivot,则继续往前移动指针j
                j--;
            }
            //当j指向元素小于pivot时，将该元素放置在i指向的位置
            array[i] = array[j];
            while (i < j && array[i] <= pivot) {
                //指针i从左向右遍历，当i指向的元素小于等于基准值pivot,则继续往后移动指针i
                i++;
            }
            //当i指向元素大于pivot时，将该元素放置在j指向的位置
            array[j] = array[i];
        }
        //最后将基准值pivot放置在i或者j的位置
        array[i]=pivot;

        if (begin < i - 1) {
            //对左侧分区进行递归
            quickSort2(array, begin, i - 1);
        }
        if (end > i + 1) {
            //对右侧分区进行递归
            quickSort2(array, i + 1, end);
        }

    }

}
